package com.ting.test.algorithms.单调栈;

import java.util.Stack;

/**
 * 给定一个只包含正数的数组arr，arr中任何一个子数组sub，一定都可以算出(sub累加和 )* (sub中的最小值)是什么，那么所有子数组中，这个值最大是多少？
 */
public class 单调栈例题2 {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 4, 2, 6, 1, 7, 0};
        int[][] result = process(arr);
    }

    private static int[][] process(int[] arr) {
        int[] sumArr = new int[arr.length];//该数组中存储了从0到i的累加和
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            sumArr[i] = sum;
        }

        Stack<Integer> stack = new Stack<Integer>();//构造一个从大到小的栈
        stack.push(arr[0]);

        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {// 当前的情况就是 当前栈顶元素arr[stack.peek()] 是最小的，

            }
            stack.push(i);
        }

        return new int[0][];
    }

}
